#include "stdafx.h"
#include "cassert"
#include "mylib.h"

void merge(int* pIn,int p,int q)
{
	int mid=(p+q)/2;
	int* a=new int[mid-p+1];
	for (int i=0;i<mid-p+1;++i)
	{
		a[i]=pIn[p+i];
	}
	int* b=new int[q-mid];
	for (int i=0;i<q-mid;++i)
	{
		b[i]=pIn[mid+1+i];
	}
	int ai=0,bi=0;
	for (int i=p;i<=q;++i)
	{
		if (ai==mid-p+1)
		{
			pIn[i]=b[bi];
			++bi;
		}
		else if (bi==q-mid)
		{
			pIn[i]=a[ai];
			++ai;
		}
		else
		{
			if (a[ai]<b[bi])
			{
				pIn[i]=a[ai];
				++ai;
			}
			else
			{
				pIn[i]=b[bi];
				++bi;
			}
		}		
	}
}

void mergesort(int* pIn,int p,int q)
{
	assert(p<=q);
	if (p==q)
	{
		return;
	}	
	int mid=(p+q)/2;
	if (p<=mid)
	{		
		mergesort(pIn,p,mid);
	}
	if (mid<q)
	{		
		mergesort(pIn,mid+1,q);
	}
	merge(pIn,p,q);
}